Construct the Lexicographically Largest Valid Sequence

搜索题，按照字典序回溯搜索就行

impl Solution {
    pub fn construct_distanced_sequence(n: i32) -> Vec<i32> {
        let mut res = vec![0;(n*2 - 1) as usize];
        search(&mut res, (1<<n)-1, 0);
        res
    }
}

fn search(arr: &mut Vec<i32>, n: usize, i: usize) -> bool {
    if n == 0 {
        return true;
    }
    if i >= arr.len() {
        return false;
    }
    if arr[i] != 0 {
        return search(arr, n, i + 1);
    }

    for j in (1..=arr.len()).rev() {
        if n&1 == 1 && j == 1 {
            arr[i] = 1;
            if search(arr, n^1, i + 1) {
                return true;
            }
            arr[i] = 0;
        }
        if (n>>(j-1)) & 1 == 1 && i + j < arr.len() && arr[i + j] == 0 {
            arr[i] = j as i32;
            arr[i + j] = j as i32;
            if search(arr, n^(1<<(j-1)), i + 1) {
                return true;
            }

            arr[i] = 0;
            arr[i + j] = 0;
        }
    }
    
    false
}